package 题目集.拓扑排序;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/course-schedule-ii/description/
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 */
public class demo01_课程表2 {
    public int[] findOrder(int n, int[][] prerequisites) {
    	int[] ins=new int[n];
    	List<Integer>[] graph=new List[n];	//图
    	for(int i=0;i<n;i++) {
    		graph[i]=new ArrayList<>();
    	}
    	for(int[] edge:prerequisites) {
    		graph[edge[1]].add(edge[0]);
    		ins[edge[0]]++;
    	}
    	int[] q=new int[n];
    	int h=0,t=0;
    	for(int i=0;i<n;i++) {
    		if(ins[i]==0) {
    			q[t++]=i;
    		}
    	}
    	int[] res=new int[n];
    	int cnt=0;
    	while(h<t) {
    		int cur=q[h++];
    		res[cnt++]=cur;
    		for(int to:graph[cur]) {
    			ins[to]--;
    			if(ins[to]==0) {
    				q[t++]=to;
    			}
    		}
    	}
    	if(t!=n) {
    		return new int[] {};
    	}
    	return res;
    }
}
